//
// Created by LiuYou on 2021/11/29.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>


static void bubbleSort2(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    // 标记: 上一趟循环是否进行过交换
    bool isSwap = true;
    for (int i = 0; i < arr.size() - 1 && isSwap; i++) {
        isSwap = false;
        // 在某一趟遍历中,如果没有可交换的,那么 isSwap = false,跳出外层循环;
        // 如果一旦进行了交换,则 isSwap = true,需要进行下一趟遍历
        for (int j = arr.size() - 1; j > i; j--) {
            if (arr[j - 1] > arr[j]) {
                std::swap( arr[j - 1], arr[j] );
                isSwap = true;
            }
        }
    }
}


/*
 * 这个冒泡排序算法可以进行优化。
 * 如果当待排序数组为1, 3, 4, 5, 6, 7, 8, 9, 2时:
 * 第1趟排序的结果为: 1 2 3 4 5 6 7 8 9
 * 此时其实序列已经完成，但是根据上述代码仍得继续遍历，直至第9趟排序。
 * 这显然是不合理的，如果我们能在代码中加入一个flag标记上一趟排序中是否进行过交换，
 * 如果进行过未进行交换，说明当前数组已经有序。
 */
static void bubbleSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    for (int i = 0; i < arr.size() - 1; i++) {
        for (int j = arr.size() - 1; j > i; j--) {
            if (arr[j - 1] > arr[j]) {
                std::swap( arr[j - 1], arr[j] );
            }
        }
    }
}


int main(int argc, char** argv) {
    {
        std::vector<int> arr{2, 1, 5, 4, 3};
        std::sort( arr.begin(), arr.end());
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
        std::cout << std::endl;
    }

    {
        std::vector<int> arr{2, 1, 5, 4, 3};
        bubbleSort( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
        std::cout << std::endl;
    }

    {
        std::vector<int> arr{2, 1, 5, 4, 3};
        bubbleSort2( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
        std::cout << std::endl;
    }


    return 0;
}
